Cyclotomic fast Fourier transforms (CFFTs) are efficient implementations ofdiscrete Fourier transforms over finite fields, which have widespreadapplications in cryptography and error control codes. They are of greatinterest because of their low multiplicative and overall complexities. However,their advantages are shown by inspection in the literature, and there is noasymptotic computational complexity analysis for CFFTs. Their high additivecomplexity also incurs difficulties in hardware implementations. In this paper,we derive the bounds for the multiplicative and additive complexities of CFFTs,respectively. Our results confirm that CFFTs have the smallest multiplicativecomplexities among all known algorithms while their additive complexitiesrender them asymptotically suboptimal. However, CFFTs remain valuable as theyhave the smallest overall complexities for most practical lengths. Our additivecomplexity analysis also leads to a structured addition network, which not onlyhas low complexity but also is suitable for hardware implementations.
展开▼
